#include <iostream>
using namespace std;
#define maxn 51
#define maxm 10001
#define maxbz 32
const int INF = 1<<28;

int n,m;
bool G[maxn][maxn][maxbz];
int dis[maxn][maxn];

void init(){
	for(int k=1;k<=maxbz;k++){
		for(int i=1;i<=n;i++){
			for(int t=1;t<=n;t++){
				for(int j=1;j<=n;j++){
					if(G[i][t][k-1] && G[t][j][k-1]){
						G[i][j][k]=true;
						dis[i][j]=1;
					}
				}
			}
		}
	}
}

void floyd(){
    for(int k=1;k<=n;k++)
	    for(int i=1;i<=n;i++)
	    	for(int j=1;j<=n;j++)
				if(dis[i][j] > dis[i][k]+dis[k][j])
					dis[i][j] = dis[i][k]+dis[k][j];
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dis[i][j]=INF;
	for(int i=0;i<m;i++){
		int u,v;
		cin>>u>>v;
		G[u][v][0]=true;
		dis[u][v]=1;
	}
	
	init();
	floyd();

	cout<<dis[1][n]<<endl;
	return 0;
}
